package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
* 返回一个表示每个字符串片段的长度的列表。
示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 划分字母区间_763 {
    public static void main(String[] args) {
        划分字母区间_763 demo = new 划分字母区间_763();
        List<Integer> ababcbacadefegdehijhklij = demo.partitionLabels("ababcbacadefegdehijhklij");
        for(int i : ababcbacadefegdehijhklij){
            System.out.println(i);
        }
    }

    /*
    * 解题思路： 划分片段， 保持顺序， 每个字母最多只能出现在一个片段中
    * 也就是说 a字母出现在 片段1 就不能再出现在片段2了。
    * 此外，划分的片段尽可能的多
    * 因为保持顺序 ，所以感觉是 给字符串加空格的样子  试试 搜索+回溯
    * */
    public List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>();
        f(S,result,0,new int[26]);
        return result;
    }

    public boolean f(String s,List<Integer> temp,int index,int[] visited){
        if(index >= s.length()){
            return true;
        }
        int[] meVisited = new int[26];
        int[] tempVisited = new int[26];
        cloneInt(visited,tempVisited);
        for(int i =index; i < s.length(); i++){
            if(visited[s.charAt(i) - 'a'] != 0 && meVisited[s.charAt(i) - 'a'] ==0){
                // 说明是该字母已经被别的片段使用过了
                // 返回的时候，应该把visited的使用痕迹清空
                cloneInt(tempVisited,visited);
                return false;
            }
            visited[s.charAt(i) - 'a'] = 1;
            meVisited[s.charAt(i) - 'a'] = 1;
            temp.add( i - index +1);
            if( f(s,temp,i+1,visited) ){
                return true;
            }else{
                // 不成功
                temp.remove( temp.size()-1);
            }
        }
        return true;
    }

    private void cloneInt(int[] source,int[] direct){
        for(int i = 0;i<source.length;i++){
            direct[i] = source[i];
        }
    }

    /*
    *  使用贪心
    *  因为一个字母 只能出现在同一个片段，也就是说，字母第一次出现的位置和最后一次出现的位置都应该包含在同一个片段中
    * 记录字母出现的最后一次的位置，我们的划分的片段长度必须大于这个这个位置（如果片段包含该字母）
    * 而且要让 片段尽可能的多，所以片段长度就要尽可能的小。
    *  我们遍历字符串S， 先得到当前字母的最远出现位置，如果当前字母是唯一的，就将其划分
    * 如果不是唯一的，那么就说明我们划分的片段最少都要到达那个位置。 那么那个位置到当前位置之中的字母的最远位置是否会超过那个位置呢？
    * 我们还需要进行判断
    * */
    public List<Integer> partitionLabels1(String S) {
        List<Integer> result = new ArrayList<>();
        int[] lastDistance = new int[26];
        int length = S.length();
        for(int i = 0; i < length ; i ++){
            lastDistance[S.charAt(i) - 'a'] = i;
        }
        int start = 0, end = 0;
        for(int i =0; i < length ; i++){
            end = Math.max(end,lastDistance[S.charAt(i) - 'a']);
            if( i == end){
                // 说明已经达到当前片段的最远距离了
                result.add(end-start+1);
                start = end +1;
            }
        }
        return result;
    }


}
